import java.util.*;
class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
public class TestDemo4B {
    //给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三
    //小结点的值为4。
   public TreeNode KthNode(TreeNode pRoot, int k){
        if(pRoot==null&&k<=0){
            return null;
        }
        Stack<TreeNode>st=new Stack<>();
        TreeNode node=pRoot;
        do {//使用do while的目标的是至少执行一次
            while(node!=null){//一直往左树遍历
                st.push(node);
                node=node.left;
            }
            if(!st.empty()){
               node= st.pop();//访问当前的节点
                k--;
            }
            if(k==0){//说明找到第k小的节点
                return node;
            }
            node=node.right;//判断当前的左树之后,再判断它的右树
        }while(node!=null||!st.empty());
        return null;
    }
    public static void main1(String[] args) {
        String str1="hello word";
        String str2="s";
        String str3="";
        for(int i=0;i< str1.length();i++){
            str2=str2+str1.charAt(i);
        }
        str3=str2;
        System.out.println(str3);
        System.out.println(str2);
    }
    public static int MoreThanHalfNum_Solution(int [] array) {
        Map<Integer,Integer>map=new HashMap<>();
        for(int i=0;i<array.length;i++){
            if(map.get(array[i])==null){
                map.put(array[i],1);
            }else{
                map.put(array[i],map.get(array[i])+1);
            }
            if(map.get(array[i])>array.length/2){
                return array[i];
            }
        }
        return 0;
    }

    public static void main2(String[] args) {
        int []array={1,2,3,2,2,2,5,4,2};
        System.out.println(MoreThanHalfNum_Solution(array));
    }
//字符串转化成数字
    public static int strToInt(String str){
       if(str==null||str.length()==0){
           return 0;
       }
       char[]array=str.toCharArray();//必须转化成数组形式
       int flag=0;//用来定义数字前面的+ -号
       if(array[0]=='-'){
           flag=-1;
           array[0]='0';//这里的目的是为了后面for循环能运行
       }
       if(array[0]=='+'){
           flag=1;
           array[0]='0';
        }
       int sum=0;
       for(int i=0;i<str.length();i++){
           if(array[i]>='0'&&array[i]<='9'){
               sum=sum*10+array[i]-'0';//字符转化成数字的公式
           }
           else{//不是数字字符就直接把和变为0,直接跳过循环
               sum=0;
               break;
           }
       }
       return sum*flag;
    }

    public static void main(String[] args) {
        String str="+1234";
        System.out.println(strToInt(str));
    }
}
class Main7{
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        String str1=sc.nextLine();
        String str2=sc.nextLine();
        char[]array1=str1.toCharArray();
        char[]array2=str2.toCharArray();
        Map<Character,Integer>map=new HashMap<>();
        for(int i=0;i<array2.length;i++){
            if(map.get(array2[i])==null){
                map.put(array2[i],1);
            }else{
                map.put(array2[i],map.get(array2[i])+1);
            }
        }String str="";
        for(int i=0;i<array1.length;i++) {
            if (map.get(array1[i]) == null) {
                str += array1[i];
            }
        }
        System.out.println(str);
    }
}
class Main8{
    //每日一题3.1
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        String str=sc.nextLine();
        String ret="";//用来记录最长的数字字符串
        String cur="";//存放每次连续的数字字符串
        int i=0;
        for(;i<str.length();i++){
            char ch=str.charAt(i);
            if(ch>='0'&&ch<='9'){//存放数字字符串
                cur=cur+ch+"";
            }else{//不是数字字符的情况，就需要判断是否大于存放最长字符串的长度（ret）。大于就重新赋值，小于就把cur置为null
                if(cur.length()>ret.length()){
                    ret=cur;
                    cur="";
                }else{
                    cur="";
                }
            }
        }//这里需要主要的是如果最长数字字符串在最后的情况（走了if就直接跳过了没有重新赋值）
        if(i==str.length()&&ret.length()<cur.length()){
            ret=cur;
        }
        System.out.println(ret);
    }
}
//计算糖果数（每日一题）4.1
class Main9{
    public static void main(String []args){
        Scanner sc=new Scanner(System.in);
        int a=sc.nextInt();
        int b=sc.nextInt();
        int c=sc.nextInt();
        int d=sc.nextInt();
        int A=(a+c)/2;
        int B=(b+d)/2;
        int C=(d-b)/2;
        if(B==(c-a)/2){
            System.out.println(A);
            System.out.println(B);
            System.out.println(C);
        }else{
            System.out.println("NO");

        }
    }
}
class Main10{
    public static void main(String []args){
        Scanner sc=new Scanner(System.in);
        int m=sc.nextInt();
        int n=sc.nextInt();
        String str="0123456789ABCDEF";//用来定义10进制之后的数
        StringBuffer str1=new StringBuffer();
        boolean flag=false;//判断是负数的情况
        if(m<0){//如果是负数,先转化成正数计算
            flag=true;
            m=-m;
        }
        while(m>0){
           str1.append(str.charAt(m%n));//从余数(从后面往前的数)
           m=m/n;
        }
        if(flag){//如果是负数,最后把负号加上去
            str1.append("-");
        }
        str1.reverse();//因为顺序是反的,要进行逆置
        System.out.println(str1);
    }
}
//每日一题(5.1)统计回文
class Main11{
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        String str1=sc.nextLine();
        String str2=sc.nextLine();
        int count=0;
        for(int i=0;i<str1.length();i++){
            StringBuffer str=new StringBuffer(str1);
            str.insert(i,str2);//向字符串中某个下标插入字符
            //这里需要定义tmp的目的是因为,使用reverse()本身也会逆置.tmp存放逆置后的字符,而原来的
            //继续由str保存着
            StringBuffer tmp=new StringBuffer(str);
           StringBuffer str5=tmp.reverse();
           //StringBuffer没有equals方法,而且 String有,所以要转化为字符串类型
            if(str5.toString().equals(str.toString())){
                count++;
            }
        }
        System.out.println(count);
    }

}
